There are conventional navigation devices and navigation systems that search map data, road data, and a desired route from a departure point to a destination point, and guide a user. Implementations of such navigation devices and navigation systems include communicating navigation systems and the like in which a mobile telephone or an automobile-mounted navigation device for guiding the driver through a route is used as a navigation terminal that sends a route search request to a route search server, receives the results of the route search request, and receives route guidance.
A communicating navigation system in particular is also used as a navigation system for a walking user. In this system, a mobile telephone or other mobile terminal is used as the navigation terminal. A navigation system used by a walking user is preferably provided with route guidance capability that includes transportation facilities, and there are navigation systems that are capable not only of searching a walking route and providing guidance, but also of storing train timetable data in a route search server and providing guidance in a route (boardable train) from a desired departure station to a desired destination point station, in addition to searching and providing guidance in a walking route.
There are also route search systems in which an airplane, a train, an electric train, a bus, or another mode of transportation is used and a route from a departure point to a destination point is searched and used for guidance. Such a route search system is generally configured to reference a traffic data DB (database) that includes traffic data of transportation facilities in database form on the basis of the departure time, departure point, destination point, arrival time, and other route search conditions specified by a user; to sequentially trace usable modes of transportation as a route that links the departure point to the destination point, including connecting routes; and to present one or a plurality of possible guidance routes (trains and other modes of transportation) that corresponds to the route search conditions. It is generally possible to specify the required time, the number of connections, the fares, and other additional route search conditions.
When the road network used for route searching in a walker navigation system or car navigation system is composed of roads A, B, and C as shown in FIG. 8, for example, the end points, intersection points, turning points, and other points of roads A, B, and C are designated as nodes; roads linking the nodes are indicated by directional links; and the road network data are composed of node data (node latitude/longitude), link data (link numbers), and link costs (distance between links or time required to travel to a link) in the form of data. Specifically, in FIG. 8, the symbols ∘ and □ indicate nodes, wherein the □ indicates an intersection of roads. Directional links between nodes are indicated by arrow lines (solid lines, dashed lines, chain double-dashed lines). Links in the upstream and downstream directions of the roads are present, but only links in the direction of the arrows are shown in FIG. 8 to simplify the diagram.
When the data of such a road network is route-searched as a database for route searching, a link connected from the node of the departure point to the node of the destination point is traced, the link cost is stored, and the route having the smallest stored link cost is searched and used for guidance.
Specifically, when a route search is performed using node AX in FIG. 8 as the departure point and node CY as the destination point, the link to node CY is traced in which road A is traveled from node AX, and a right turn into road C is made at the second intersection point, then the link cost is stored and the route having the smallest stored value for the link cost is searched and used for guidance. Other routes from node AX to node CY are not shown in FIG. 8. However, other routes actually exist, and routes whereby it is possible to reach node CY from node AX are therefore searched in the same manner, and the route having the smallest link cost among the searched routes is determined to be the optimum route. This technique is in accordance with the publicly known technique known as Dijkstra's method.
In a road network such as the one shown in schematic fashion in FIG. 8, the link costs are fixed, the stored link cost is an item of uniquely determined static network data when the route is determined, and the amount of data is also proportional to the amount of data in the road network.
In contrast, when the traffic network data of a transportation facility are composed of transportation lines A, B, and C as shown in FIG. 9, for example, train stations (airports in the case of an airplane route) provided to the transportation lines A, B, and C are designated as nodes, intervals linking the nodes are indicated by directional links, and the road network data are composed of node data (node latitude/longitude) and link data (link numbers. In FIG. 9, the symbols ∘ and □ indicate nodes, wherein the □ indicates a connection point (train-changing station or the like) between transportation routes, and directional links between nodes are indicated by arrow lines (solid lines, dashed lines, chain double-dashed lines). Links in the upstream and downstream directions of the roads are present, but only links in the direction of the arrows are shown in FIG. 9 to simplify the diagram.
However, the link costs in a traffic network of a transportation facility are fundamentally different from those of a road network. Specifically, the link costs in the road network are fixed and static, whereas the traffic network of the transportation facility has a plurality of trains or aircraft (trains, aircraft, and other routes are referred to hereinafter as modes of transportation) moving through the transportation lines, as shown in FIG. 9. The times of departure from the nodes of each mode of transportation are specific, as are the times of arrival at the subsequent nodes (specified in the timetable data and traffic data). There are also cases in which the routes do not necessarily link to adjacent nodes. This situation occurs in the case of express trains and local trains, for example. In such a case, a plurality of different links exists on the same transportation line, and the time required to travel between nodes may change according to the mode of transportation.
The example of the traffic network of the transportation facility shown in FIG. 9 includes a plurality of transportation modes (routes) Aa through Ac in the same link of a transportation line A, and a plurality of transportation modes (routes) Ca through Cc in a transportation line C. Accordingly, the traffic network of the transportation facility differs from a simple road network; the amount of data relating to nodes, links, and link costs therein is proportional to the sum total of the transportation modes (routes of individual aircraft, trains, and the like); and the amount of network data is extremely large in comparison to the amount of road network data. A correspondingly large amount of time is therefore needed to perform a route search.
All modes of transportation that can be used (ridden) to travel from a departure point to a destination point must be searched, and a transportation mode that satisfies the search conditions must be specified in order to search the route from a certain departure point to a certain destination point using the type of transportation facility traffic network data described above.
For example, in FIG. 9, a route search may be performed so that the departure point is node AX of transportation line A, a certain departure time is specified, and the destination point is node CY of transportation line C. In this case, all the transportation modes subsequent to the departure time among the transportation modes Aa through Ac traveling on transportation line A are selected as sequential departure time routes. Among the transportation modes Ca through Cc traveling on transportation line C, the combination of all transportation modes subsequent to the time at which boarding is possible in a connecting node is searched on the basis of the time of arrival at the connecting node to transportation line C; the time required for each route, the number of transfer connections, and other information is added together; and guidance is provided.
The type of route search described above differs from a route search by the Dijkstra method in a simple road network, the combination of transportation modes (routes of individual aircraft, trains, and the like) becomes extremely large, and the time required for the route search increases, as previously described. An example of such a route search using the data of a transportation facility traffic network is disclosed in Non-patent Document 1 described below (Kikuchi, “Method of searching an optimal connecting sequence for rail/air service on the basis of dynamic network representation, and actual application thereof,” Information Processing Society of Japan, April 1997, Vol. 38, No. 4, pp. 915-926). The term “dynamic network” refers to a network formed by sequentially adding related nodes and links together with time.
In a search of a route that uses a transportation facility, there may be cases in which a transportation mode (individual aircraft, train, electric train, or bus) is selected that satisfies the search conditions for route guidance, but the specified aircraft, train, electric train, or bus is a transportation mode that operates with reserved seating, all of the reserved seats are booked, and there are no unoccupied seats. In such cases, the aircraft, train, electric train, or bus (transportation mode) is essentially excluded from the guidance route. The presence of unoccupied reserved seats is then added as a search condition, and a reservation system for performing a route search is also furnished as described below. In the present invention, the inclusion of the presence of unoccupied seating as a search condition is referred to as a seating condition, and the seating condition is included in the search conditions when the search conditions are referred to, unless otherwise specified.
Aircraft reservation systems, rail reservation systems, and the like are known as systems that use the presence of unoccupied seating as a condition for searching usable modes of transportation (aircraft or trains) when a mode of transportation is used to travel from a departure point to a destination point. Such a reservation system is generally configured so that a computer device that has a reservation information database and is installed in a reservation center operated by the transportation facilities is accessed to search transportation modes that have unoccupied seats and to make a reservation. The terminal devices are installed in the reservation windows of train stations or travel vendors, but it has recently become possible for the aforementioned computer device to be accessed to make a reservation via the Internet from a user's computer device or mobile telephone.
Such a reservation system differs from a navigation system for searching a plurality of possible transportation modes and providing guidance, and is generally configured so that a search is performed interactively through the intervention of the operator so as to change the search conditions and to present the reservation condition of the next possible option when there are no unoccupied seats in the train that corresponds to the search conditions, the seating condition is not satisfied, and a reservation cannot be made. Reservation systems are also often operated in separate, independent forms for each transportation facility, and a user must either make a reservation with the necessary reservation system separately, or request a search and reservation from an operator using the reservation system of each transportation facility at the window of a travel agency.
The system disclosed in Patent Document 1 (Japanese Patent Application Laid-open No. 4-70963) below, for example, is known as a transportation reservation system that overcomes the inconvenience described above. This transportation reservation system is composed of a transportation information management device for managing the information of all transportation facilities, a scheduling device that uses the transportation information management device to perform scheduling and determine a transportation mode to the destination point through various combinations of various transportation facilities, and a reservation device for making a reservation for the mode of transportation determined by the scheduling device.
In this transportation reservation system, a subsequent transportation facility (route) must be searched again when a reservation cannot be made due to a lack of unoccupied seating in the transportation facility (route) that was searched according to a certain search condition, as described in the lower left column of page 3 of the abovementioned publication: “When there are no unoccupied seats, and a reservation cannot be made (step 107: NO), the transportation facility having the next shortest route is searched by the shortest-route scheduler 11, and scheduling is performed (step 103).”
Patent Document 2 (Japanese Patent Application Laid-open No. 2003-44553) below discloses an itinerary-providing method and an itinerary-providing device. The device is configured so as to be capable of providing detailed travel guidance even when used on a network. Specifically, when the user of a browsing terminal inputs/selects the conditions needed to form an itinerary by using a group of condition setting buttons on a menu screen, and presses a search button, an itinerary formulation request is transmitted to an itinerary service center, and an itinerary formed by the center is displayed in a display area. When the plan shown in the display is changed using a group of modifying buttons or slide buttons, a request to change the plan is transmitted to the center, and an itinerary that is redesigned by the center is displayed in the display area.
In this device, when ticket arrangements or a reservation for reserved seating must be made in order to use the determined travel service, an instruction for confirming the unoccupied seating condition of the travel service (transportation mode) is issued to a schedule search/reservation request unit of the transportation facility via an instruction transmitting/receiving unit. The schedule search/reservation request unit of the transportation facility is then made to access the transportation facility reservation center and confirm the unoccupied seating condition of the travel service. As a result, when it is confirmed that all seats are occupied, a travel service among those that are traveling on the aforementioned route segment, and are scheduled to arrive sooner than the aforementioned scheduled arrival time, are searched to find the travel service having the next closest scheduled arrival time to the aforementioned scheduled arrival time of the travel service for which unoccupied seating could not be confirmed. The travel service thus searched is determined to be embarking in the aforementioned route segment, and the unoccupied seating condition is confirmed in the same manner as described above. This routine is continued until a travel service is found that has unoccupied seating.
A navigation system and a route search method program are disclosed in Patent Document 3 (Japanese Patent Application Laid-open No. 2004-206482) described below. This navigation system has a search condition setting routine device for setting a route search segment as a search condition, a route search routine device for searching a route on the basis of the set search condition, a reserved seating line determination routine device for determining whether the searched route includes at least one or more reserved seating lines, and a notification routine device for notifying an operator of a searched route that includes a reserved seating line when the searched route includes at least one or more reserved seating lines. When the searched route includes at least one or more reserved seating lines, the operator is notified of the searched route that includes a reserved seating line. This navigation system makes it possible to secure a seat for use in a public transportation facility on the searched route.    [Non-Patent Document 1]    Kikuchi, “Method of searching an optimal connecting sequence for rail/air service on the basis of dynamic network representation, and actual application thereof,” Information Processing Society of Japan, April 1997, Vol. 38, No. 4, pp. 915-926.    [Patent Document 1]    Japanese Patent Application Laid-open No. 4-70963 (FIG. 1)    [Patent Document 2]    Japanese Patent Application Laid-open No. 2003-44553 (FIG. 1, paragraph [0133])    [Patent Document 3]    Japanese Patent Application Laid-open No. 2004-206482